package chain;


/**
 	141：https://leetcode-cn.com/problems/linked-list-cycle/
 * @author wxh
 */
public class Solution_3 {

	public boolean hasCycle(ListNode head) {
		ListNode slow = head; // 慢指针
		ListNode fast = head; // 快指针
		// 如果有环，则快慢指针一定会相遇，因为每走1轮，fast 与 slow 的间距 +1，fast 终会追上slow
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;

			// 快慢指针相遇，说明循环
			if (slow == fast) {
				return  true;
			}
		}
		return false;
	}

	class ListNode {
		int val;
		ListNode next;
		ListNode(int x) {
			val = x;
		}
	}

}